package 栈;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class No144二叉树的前序遍历 {

    public List<Integer> preorderTraversal(TreeNode root) {

        if(root==null)
            return new ArrayList<Integer>();

        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()){
            /**
             * 先吃自己再吃左右,得先吃
             */
            TreeNode pop = stack.pop();
            list.add(pop.val);//先吃
            if(pop.right!=null)
                stack.add(pop.right);
            if(pop.left!=null)//后进先出,所以后放左
                stack.add(pop.left);
        }

        return list;
    }

}
